#!/usr/bin/python3
# -*- coding: utf-8 -*-
# Author: Andevilin
# 功能：迷宫游戏的主程序，实现游戏的主窗口绘制与按键处理等功能

import random
import time
from itertools import count
from tkinter import messagebox
from collections import deque
import cell
import graphics
from cell import L_WALL, R_WALL, U_WALL, D_WALL

DELAY_TIME = 30


class Game(object):
    """docstring for Game"""
    DEBUG = 0
    # 记录迷宫格子的二维列表
    mz = []
    # 记录机器走迷宫的路径
    visited = []
    # 记录玩家走迷宫的路径
    visited2 = []
    # 记录游戏开始的时间
    start_time = 0
    # 记录游戏结束的时间
    end_time = 0

    # 生成迷宫使用的队列
    class PlayerSet(object):
        def __init__(self):
            self.celll = []

        def add(self,pos):
            if pos not in self.celll:
                self.celll.append(pos)

        def pop(self):
            radnum = random.randint(0, len(self.celll) - 1)
            item = self.celll.pop(radnum)
            return item

        def len(self):
            return len(self.celll)

        def clear(self):
            self.celll.clear()

    def __init__(self, field, x, y):
        self.exit = None
        self.field = field
        self.field_height = x
        self.field_width = y
        self.walker = (0, 0)
        self.Walker = (0, 0)

        # 生成迷宫
        for i in range(0,x):
            # 增加一行
            self.mz.append([])
            # 向每一行里加上列数个格子
            for j in range(0,y):
                cel = cell.Cell()
                self.mz[i].append(cel)
        self.display = graphics.Graphics(field, x, y)

    def cleraGame(self):
        # 初始化开始时间和结束时间
        # print("test")
        self.start_time = 0
        self.end_time = 0
        # 初始化walker的坐标
        self.walker = (0, 0)
        # 设置walker的坐标
        self.display.setWalker(0,0)
        # 清空显示
        self.display.clear()
        # 遍历整个field
        for i in range(0,self.field_height):
            for j in range(0,self.field_width):
                # 清空每个格子
                # print(type(self.mz[i][j]))
                self.mz[i][j].clear()

    # 生成迷宫
    def drawGame(self):
        # 随机选择一个点作为起点，并且标记为已访问
        # print("test")
        col = random.randint(0,self.field_width - 1)
        row = random.randint(0,self.field_height - 1)
        self.mz[row][col].visit()
        # print("初始点：",row,col)

        # 将起点的格子加入队列中
        front = self.PlayerSet()
        front = self.addToFront(front, (row, col))
        # print(front)
        # print(front.len())
        # print(self.DEBUG)
        while front.len() > 0:
            # 选择一个格子，作为下一步访问的格子，并标记为已访问
            row, col = front.pop()
            self.mz[row][col].visit()
            self.breakWall(row, col)

            front = self.addToFront(front, (row, col))

            # DEBUG模式
            # print(self.DEBUG)
            if self.DEBUG >= 1:
                print("当前front的大小",front.len())
            if self.DEBUG > 1:
                messagebox.showinfo("Break","Continue")
        if self.DEBUG >= 1:
            print("生成数量：",count)
            input("按任意键退出")
        # print(front.len())
        # 随机选择一个入口的位置,在最下面一行格子里选,并将其底边去掉
        row = self.field_height - 1
        col = random.randint(0,self.field_width - 1)
        self.display.breakWall(row, col,'D')
        
        # 设置玩家的初始位置在入口所在的格子
        self.walker = (row, col)
        self.display.setWalker(row, col)
        
        # 随机选择一个出口的位置,在最上面一行格子里选,并将其顶边去掉
        row = 0
        col = random.randint(0,self.field_width - 1)
        self.mz[row][col].breakWall(U_WALL)
        self.display.breakWall(row, col,'U')
        self.exit = (row, col)
        self.display.setGoal(row, col)


    # 实现玩家控制小点的移动功能
    def move(self, mv):
        # 记录游戏开始的时间
        if self.start_time == 0:
            self.start_time = time.time()
        # 超时判断
        if (self.end_time - self.start_time)>= DELAY_TIME:
            messagebox.showinfo("您已超时！","对不起，您已超时！下次加油！")

        # 每次移动小点，记录最后一次移动小点的时间
        self.end_time = time.time()
        # print(self.start_time, self.end_time)

        # 获取当前小点的位置
        row, col = self.walker
        self.visited2.append(self.walker)
        if mv == 'U':
            # 判断是否可以向上移动
            if self.mz[row][col].hasWall(U_WALL):
                messagebox.showerror("此路不通！","些路不通，请重新选择一条路！")
            else:
                # 判断是否到达出口
                x,y = self.exit
                if (x == row) and (y == col):
                    messagebox.showinfo("恭喜您！",f"恭喜您，成功走出迷宫！"
                                                  f"用时{round((self.end_time - self.start_time), 2)}秒！")
                    # 返回False 等待游戏
                    return False

                # 向上移动
                self.walker = (row - 1, col)
                self.display.moveWalker(row - 1, col)
        elif mv == 'D':
            # 判断是否可以向下移动
            if self.mz[row][col].hasWall(D_WALL):
                messagebox.showerror("此路不通！","些路不通，请重新选择一条路！")
            else:
                # 向下移动
                self.walker = (row + 1, col)
                self.display.moveWalker(row + 1, col)
        elif mv == 'L':
            # 判断是否可以向左移动
            if self.mz[row][col].hasWall(L_WALL):
                messagebox.showerror("此路不通！","些路不通，请重新选择一条路！")
            else:
                # 向左移动
                self.walker = (row, col - 1)
                self.display.moveWalker(row, col - 1)
        elif mv == 'R':
            # 判断是否可以向右移动
            if self.mz[row][col].hasWall(R_WALL):
                messagebox.showerror("此路不通！","些路不通，请重新选择一条路！")
            else:
                # 向右移动
                self.walker = (row, col + 1)
                self.display.moveWalker(row, col + 1)
        # up = self.mz[self.walker[0]][self.walker[1]].noWall(cell.U_WALL)
        # if up:
        #     print(f'({self.walker[0],self.walker[1]})上边没有墙')
        # else:
        #     print(f'({self.walker[0],self.walker[1]})上边有墙')
        # down = self.mz[self.walker[0]][self.walker[1]].noWall(cell.D_WALL)
        # if down:
        #     print(f'({self.walker[0],self.walker[1]})下边没有墙')
        # else:
        #     print(f'({self.walker[0],self.walker[1]})下边有墙')
        # left = self.mz[self.walker[0]][self.walker[1]].noWall(cell.L_WALL)
        # if left:
        #     print(f'({self.walker[0],self.walker[1]})左边没有墙')
        # else:
        #     print(f'({self.walker[0],self.walker[1]})左边有墙')
        # right = self.mz[self.walker[0]][self.walker[1]].noWall(cell.R_WALL)
        # if right:
        #     print(f'({self.walker[0],self.walker[1]})右边没有墙')
        # else:
        #     print(f'({self.walker[0],self.walker[1]})右边有墙')

        # 表示还没到达出口，继续等待游戏
        return False

    # 实现自动寻路走出迷宫功能
    def auto(self, x, y):
        # 获取当前小点的位置
        start_pos = self.walker
        # 获取出口的位置
        end_pos = self.exit
        #print("当前位置：", row, col,",","出口位置：", exit_x, exit_y)
        # self.answer(x1,y1, x, y)

        # 调用广度优先搜索算法，获取从起点到终点的路径并存入autopath列表
        autopath = self.findPath(start_pos, end_pos)

        # 根据路径绘制小点的位置
        for pos in autopath:
            # print(pos)
            if pos != start_pos:
                # 更新小点所在位置
                self.walker = pos
                # 在游戏界面显示出新的位置
                self.display.moveWalkerAnswer(pos[0], pos[1])
                # time.sleep(0.5)



    # 实现自动寻路的广度优先搜索算法 （bfs）
    def findPath(self, start, end):
        # 定义四个可能的移动方向：上，下，左，右
        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        # 定义一个队列，用于存储待访问的节点
        queue = deque([start])
        # print(queue)

        # 定义一个字典，用于存储每个节点的前驱节点，用于重建路径
        came_from = {start: None}

        # print(self.mz[start[0]][start[1]].noWall(L_WALL))
        # print(self.mz[start[0]][start[1]].noWall(R_WALL))
        # print(self.mz[start[0]][start[1]].noWall(U_WALL))
        # print(self.mz[start[0]][start[1]].noWall(D_WALL))

        while queue:
            # print(came_from)
            # 从队列中取出一个节点
            current = queue.popleft()
            # print(queue)
            # 如果当前节点是目标节点，则找到了路径，开始重建路径,并返回路线
            if current == end:
                return self.reconstructPath(came_from, start, end)

            # 遍历当前节点的所有能通过的相邻节点
            for dir in directions:
                # 计算相邻节点的位置
                next_pos = (current[0] + dir[0], current[1] + dir[1])
                # 判断相邻节点是否在迷宫范围内，并且相邻节点是否可以通过
                if self.is_valid(current, dir):
                    # print('可以通行')
                    # 如果下一个节点不在came_from字典中，则将其加入队列，并记录其前驱节点
                    if next_pos not in came_from:
                        queue.append(next_pos)
                        # print(queue)
                        came_from[next_pos] = current

        # 如果队列为空，说明没有找到路径
        return []



    # 迷宫中小格子的边框与路径生成方法
    def addToFront(self, front, cel_pos):
        # 获取当前单元格的位置
        # print("atf")
        r, c = cel_pos
        # 如果当前单元格的上方不是边界
        if r!= 0:
            # 如果上方单元格未被访问过
            if self.mz[r - 1][c].visited() == False:
                # 将上方单元格的位置添加到front中
                front.add(((r - 1), c))
        # 如果当前单元格的下方不是边界
        if r != self.field_height - 1:
            # 如果下方单元格未被访问过
            if self.mz[r + 1][c].visited() == False:
                # 将下方单元格的位置添加到front中
                front.add(((r + 1), c))
        # 如果当前单元格的左方不是边界
        if c != 0:
            # 如果左方单元格未被访问过
            if self.mz[r][c - 1].visited() == False:
                # 将左方单元格的位置添加到front中
                front.add((r, c - 1))
        # 如果当前单元格的右方不是边界
        if c != self.field_width - 1:
            # 如果右方单元格未被访问过
            if self.mz[r][c + 1].visited() == False:
                # 将右方单元格的位置添加到front中
                front.add((r, c + 1))
        # 返回front
        return front

    # 打通一条可以走通的路径
    def breakWall(self, row, col):
        breakable = self.PlayerSet()

        # 检查上方格子是否可以打通
        if row != 0:
            if self.mz[row - 1][col].visited():
                breakable.add((row - 1, col))
        # 检查下方格子是否可以打通
        if row != self.field_height - 1:
            if self.mz[row + 1][col].visited():
                breakable.add((row + 1, col))
        # 检查左方格子是否可以打通
        if col != 0:
            if self.mz[row][col - 1].visited():
                breakable.add((row, col - 1))
        # 检查右方格子是否可以打通
        if col != self.field_width - 1:
            if self.mz[row][col + 1].visited():
                breakable.add((row, col + 1))

        # 随机选取一个格子
        r, c = breakable.pop()

        # 如果选取的格子与当前格子同行
        if r == row:
            # 如果选取的格子在当前格子的左边
            if c < col:
                # 打通当前格子的左墙和选取格子的右墙
                self.mz[row][col].breakWall(cell.L_WALL)
                self.mz[r][c].breakWall(cell.R_WALL)
                # 连接当前格子和选取的格子
                self.display.connectCells(row, col, r, c)
                # print("test")
            # 如果选取的格子在当前格子的右边
            else:
                # 打通当前格子的右墙和选取格子的左墙
                self.mz[row][col].breakWall(cell.R_WALL)
                self.mz[r][c].breakWall(cell.L_WALL)
                # 连接当前格子和选取的格子
                self.display.connectCells(row, col, r, c)
        # 如果选取的格子与当前格子不同行
        else:
            # 如果选取的格子在当前格子的上方
            if r < row:
                # 打通当前格子的上墙和选取格子的下墙
                self.mz[row][col].breakWall(cell.U_WALL)
                self.mz[r][c].breakWall(cell.D_WALL)
                # 连接当前格子和选取的格子
                self.display.connectCells(row, col, r, c)
            # 如果选取的格子在当前格子的下方
            else:
                # 打通当前格子的下墙和选取格子的上墙
                self.mz[row][col].breakWall(cell.D_WALL)
                self.mz[r][c].breakWall(cell.U_WALL)
                # 连接当前格子和选取的格子
                self.display.connectCells(row, col, r, c)

        # DEBUG模式
        if self.DEBUG > 1:
            print("Clear breakWall:  size = ",breakable.len())

    # 用于根据前驱节点字典重建路径
    def reconstructPath(self, came_from, start, end):
        # 将当前节点设为目标节点
        current = end
        # 创建一个空路径列表
        path = []
        # 当当前节点不等于起始节点时，执行循环
        while current != start:
            # 将当前节点添加到路径列表中
            path.append(current)
            # 将当前节点设为前一个节点
            current = came_from[current]
        # 将起始节点添加到路径列表中
        path.append(start)
        # 将路径列表反转
        path.reverse()
        # 返回路径列表
        return path

    # 检查该节点是否在迷宫的范围，并且能否通过
    def is_valid(self,current,  dir):
        up = self.mz[current[0]][current[1]].noWall(U_WALL)
        down = self.mz[current[0]][current[1]].noWall(D_WALL)
        left = self.mz[current[0]][current[1]].noWall(L_WALL)
        right = self.mz[current[0]][current[1]].noWall(R_WALL)
        if dir[0] == -1:
            return current[0] - 1 >= 0 and up
        if dir[0] == 1:
            return current[0] + 1 < self.field_height and down
        if dir[1] == -1:
            return current[1] - 1 >= 0 and left
        if dir[1] == 1:
            return current[1] + 1 < self.field_width and right

